package algorithm.backtracing;

/**
 * leetcode: https://leetcode.com/problems/valid-sudoku/
 * Difficult : Medium
 *
 * 验证数独的有效性
 * 数独不一定非得被解了，但是必须验证这个数独是有效的，也就是说每一行一列一个区块，数字都必须是0~9内并且唯一
 * 不需要校验数独一定可解
 *
 * Created by yzy on 2021-02-05 17:28
 */
public class ValidSudoku {
    public static void main(String[] args) {
        char[][] board = new char[9][9];
        board[0] = new char[]{'8','3','.','.','7','.','.','.','.'};
        board[1] = new char[]{'6','.','.','1','9','5','.','.','.'};
        board[2] = new char[]{'.','9','8','.','.','.','.','6','.'};
        board[3] = new char[]{'8','.','.','.','6','.','.','.','3'};
        board[4] = new char[]{'4','.','.','8','.','3','.','.','1'};
        board[5] = new char[]{'7','.','.','.','2','.','.','.','6'};
        board[6] = new char[]{'.','6','.','.','.','.','2','8','.'};
        board[7] = new char[]{'.','.','.','4','1','9','.','.','5'};
        board[8] = new char[]{'.','.','.','.','8','.','.','7','9'};

        boolean succ = isValidSudoku(board);
        System.out.println(succ);
    }

    public static boolean isValidSudoku(char[][] board) {
        for(int i=0; i<9; i++){
            boolean checkPass = checkLine(i,board) && checkRow(i,board) && checkBlock(i,board);
            if(!checkPass){
                return false;
            }
        }
        return true;
    }

    /**
     * 【注意】
     * 由于数字是 1~9，所以应该建立的check数组得为10，才能方得下索引为9的数据
     * @param num
     * @param board
     * @return
     */
    private static boolean checkLine(int num, char[][] board){
        int[] arr = new int[10];
        for(int i=0; i<board[num].length; i++){
            char c = board[num][i];
            int n = c - '0';
            if(n>0&&n<10 && arr[n]++ >= 1){
                return false;
            }
        }
        return true;
    }

    private static boolean checkRow(int num, char[][] board){
        int[] arr = new int[10];
        for(int i=0; i<board.length; i++){
            char c = board[i][num];
            int n = c - '0';
            if(n>0&&n<10 && arr[n]++ >= 1){
                return false;
            }
        }
        return true;
    }

    private static boolean checkBlock(int num, char[][] board){
        int[] arr = new int[10];
        int xPower = num / 3;
        int yPower = num % 3;
        for(int i=0; i<3; i++){
            int xIdx = i + xPower * 3;
            for(int j=0; j<3; j++){
                int yIdx = j + yPower * 3;
                char c = board[xIdx][yIdx];
                int n = c - '0';
                if(n>0&&n<10 && arr[n]++ >= 1){
                    return false;
                }
            }
        }
        return true;
    }


}
